package com.xw.class04;

/**
 * @author: xw
 * @create: 2022/9/20 17:21
 * @description: 逆序对
 */
public class Code03_ReverseOrder {

    public static int reverseOrder(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int left, int right) {
        if (left == right){
            return 0;
        }
        int mid = left + ((right - left)>>1);
        return process(arr,left,mid) +
                process(arr,mid+1,right) +
                merge(arr,left,mid,right);
    }

    private static int merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right-left+1];
        int i = 0;
        int p1 = left;
        int p2 = mid +1;
        int res = 0;
        while(p1 <= mid && p2 <= right){
            res += arr[p1] > arr[p2] ? (right-p2+1)  : 0;
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p2 <= right){
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {3,1,2,6,4,6,2,4};
        System.out.println(reverseOrder(arr));

    }
}
